(1) Technical Field
The present invention is related to the field of controlling movement for large groups of agents in physical and computing environments. More specifically, this disclosure presents a method for controlling the movement of a plurality of agents using low bandwidth communications.
(2) Discussion
Over the past few decades, approaches to controlling agents have focused on individual agents and a centralized database. As a result, traditional control of agents and sensors has taken the form of a single mobile agent or a small number of agents using a pre-constructed digital map to aid in path planning and control of the agents or agents. It was necessary to develop a large centralized terrain/environment database to serve as the pre-constructed digital map for geometric computations. Typical computations at these centralized databases include determination of shortest path to destination, and routes to destinations. Information relevant to these approaches can be found in U.S. Pat. Nos. 4,119,900; 4,882,694; 5,165,064; and 5,170,351. However, the agent control systems disclosed in each one of these references suffers from one or more of the following disadvantages: 1) the agent is oriented within a fixed surface area; 2) the system only allows for narrow applications of distance-maintenance; 3) the system requires a master station and a means to locate the agent; 4) the system requires cameras to locate the mobile agents; 5) the employment of an array of ultrasonic transducers is required on mobile agents; 6) each agent is individually controlled and monitored by a large master station database; and 7) each agent monitors a sector of workspace. An alternative technique, termed the gas-expansion method, was provided in the parent patent to this invention.
Although more efficient than previous techniques, the strict gas-expansion method, for particular configurations of the attraction/repulsion maps, may not facilitate an efficient expansion into unoccupied space. In the gas-expansion method, agents are xe2x80x9cpushedxe2x80x9d into unoccupied space by other agents. An agent determines the distance to every other agent with respect to a simple attraction range distance and a repulsion range distance. For each agent, a motion vector is generated, towards the agent if its distance is further than the attraction range and away from the agent if its distance is greater than the repulsion range. These vectors are then combined to form a resultant motion vector. The resulting motion vector in the gas-expansion technique is the sum total xe2x80x9cpushxe2x80x9d of all agents that are observed by the agent that is to move.
A need exists in the art for a technique that more efficiently monitors the pattern or layout of occupied and unoccupied space surrounding the agent to facilitate a more direct and efficient expansion into unoccupied space.
One embodiment of the present invention is a method for directing the movement of an agent in an environment. The method comprises the steps of determining a first zone and direction to the objects in at least a portion of the environment around the agent. The next step in the method is to determine whether the agent is surrounded by any objects. If the agent is surrounded by objects, the next step of the method will be to keep the agent stationary. However, if the agent is not surrounded by objects, the next step in the method determines whether the closest object is beyond a first zone from the agent. If the closest object is beyond the first zone, the next step in the method will be to move the agent toward a portion of the environment having the greatest object-saturation. If the closest object is within the first zone, the next step in the method will be to move the agent toward a portion of the environment having the least object-saturation.
In a further aspect of the method of the present invention, an additional step takes place when the closest object is within a second zone and where the second zone is within the first zone. In this case, the next step in the method will be to move the agent toward a portion of the environment having the least object-saturation. When the closest object is beyond the second zone, but within the first zone, the next step in the method will be to keep the agent substantially stationary.
In a still further aspect, the method comprises a further step when the closest object is within an immediate zone, and where the immediate zone is within the second zone. In this case the next step of the method will be to perform an adjustment measure with respect to the closest object.
In a still further aspect of the present invention, an additional step of the method occurs wherein the portion of the environment having the least-object saturation is determined by searching for a minimally populated region outside the second zone having a minimum set of objects.
In yet another aspect of the method of the present invention, the environment is a physical space, and wherein the minimally populated region is a minimally populated angular region.
In another aspect of the method of the present invention, the minimally populated angular region must exceed a minimum angular value before the agent moves toward the portion of the environment having the least object-saturation.
In a further aspect of the method of the present invention, the minimally populated angular region is a maximum unoccupied angular region.
In a still further aspect of the method of the present invention, the environment is discretized into bins, and wherein the portion of the environment having the least-object saturation is determined by finding the minimally populated bin.
In another aspect of the method of the present invention, the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the least-object saturation may be varied.
In another aspect of the method of the present invention, the portion of the environment having the greatest object-saturation is determined by searching for a populated region outside the first zone having a maximum set of objects.
In another aspect of the method of the present invention, the environment is a physical space, and wherein the populated region is a maximally populated angular region.
In another aspect of the method of the present invention, the maximally populated angular region must be less than a maximum angular value before the agent moves away from the portion of the environment having the greatest object-saturation.
In another aspect of the method of the present invention the environment is discretized into bins, and wherein the portion of the environment having the greatest-object saturation is determined by finding a maximally populated bin with a maximum set of objects.
In another aspect of the method of the present invention the bins may be combined into super bins, whereby a resolution used for determining the portion of the environment having the greatest-object saturation may be varied.
In another aspect of the method of the present invention the adjustment measure is performed by determining a maximally opposite angular direction from the object within the immediate zone and moving the agent a distance in the maximally opposite direction.
In another aspect of the method of the present invention, the objects are classified into multiple classes, and wherein a first zone, a second zone, and an immediate zone are independently assigned to each class.
In another aspect of the method of the present invention, the first zone, the second zone, and the immediate zone are independently adjustable based on at least one characteristic selected from a group consisting of environmental characteristics and task characteristics.
In another aspect of the method of the present invention, the classes of objects include other agents and obstacles.
In another aspect of the method of the present invention, the adjustment measure varies according to the class of object in the immediate zone.
In another aspect of the method of the present invention, the agents are mobile computing devices, and wherein the mobile computing devices move within an environment in at least two dimensions.
In another aspect of the method of the present invention, at least one of the minimally populated angular region and the maximally populated angular region are adjusted based on at least one factor selected from a group consisting of object class, environmental characteristics, and task characteristics.